/*
 * @lc app=leetcode id=92 lang=cpp
 *
 * [92] Reverse Linked List II
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {

        if (!head || m >= n || m < 1 || n < 1) {
            return head;
        }

        int h = m, t = n;
        ListNode* fakeNode = NULL;
        ListNode* node = NULL;
        ListNode* tail = NULL;

        if (m == 1) {
            fakeNode = new ListNode(-1);
            fakeNode->next = head;
            node = fakeNode;
        } else {
            node = head;
            while(node->next && --h > 1) {
                node = node->next;
            }
        }

        tail = head;
        while(tail && n-- > 0) {
            tail = tail->next;
        }
        
        node->next = reverse(node->next, tail);
        if (m==1) {
            head = fakeNode->next;
            delete fakeNode;
        }
        return head;
    }

    ListNode* reverse(ListNode *node, ListNode *tail) {
        ListNode* prev = NULL;
        ListNode* tmp;
        ListNode* oldHead = node;

        while(node != tail) {
            tmp = node->next;
            node->next = prev;
            prev = node;
            node = tmp;
        }
        if (oldHead) {
            oldHead->next = tail;
        }

        return prev;
    }
};

